home *** CD-ROM | disk | FTP | other *** search
/ Language/OS - Multiplatform Resource Library / LANGUAGE OS.iso / clean / sun3.lha / Sun3 / pardemos / parqs.icl next >
Text File  |  1992-08-07  |  4KB  |  117 lines
  1. MODULE parqs;
  2.  
  3. <<
  4. Parallel quicksort.
  5.  
  6. This program sorts a list of integers using quicksort. When the lists
  7. are bigger than a certain threshold during the sorting process, the
  8. sorting will be done using divide and conquer parallellism. Otherwise
  9. a sequential version of the quicksort algorithm will be called.
  10. The result of the program is a sorted list of integers.
  11.  
  12. Run the program with the show constructors option on.
  13. >>
  14.  
  15. IMPORT deltaI;
  16.  
  17. TYPE
  18.  
  19. <<
  20. For the parallel quicksort algorithm it is more convenient to use
  21. a tree to represent the result. The sequential version uses lists
  22. to represent the result, so the result of the sorting process will be
  23. a binary tree filled with integers of which the leafs are lists of
  24. integers of size < Threshold. At the end of the sorting process this
  25. tree will be transformed into a list again.
  26. >>
  27.  
  28. ::  SortResult x -> Tree x (SortResult x) (SortResult x)
  29.                  -> Leaf [x];
  30.  
  31.  
  32. MACRO
  33.  
  34.     Threshold -> 7; == Lists of length >= Threshold will be sorted in parallel
  35.     
  36.  
  37. RULE
  38.  
  39. ==  The list that will be sorted.
  40.  
  41. ::  UnsortedList -> [INT];
  42.     UnsortedList -> [1,3,6,4,2,7,3,12,5,17,4,987,3,2,17,4,5,6,93,5,28, 
  43.                      16,4,11,89,1,30,12,78,35,27,85,7,48,63,21,7,8,2,
  44.                      10,7,20,832,92,111,67,21,8438,12,1,26,53,51,
  45.                      114,12,23,68,38,1099,0,12,-12,7,3,15,101,23,4,
  46.                      77,1,3,5,3,1,67,123,1,-9,0,7,4,53,52,51,31];
  47.  
  48. <<
  49. Miscellaneous list functions.
  50. >>
  51.  
  52. ==  Is the lenght of the list smaller than n?
  53.     
  54. ::  Smaller [x] INT  -> BOOL;
  55.     Smaller [] n     -> TRUE;
  56.     Smaller [f|r] 0  -> FALSE;
  57.     Smaller [f|r] n  -> Smaller r (-- n);
  58.  
  59. ==  FastAppend is fast because of the local !-annotation.
  60.     
  61. ::  FastAppend [x] [x] -> [x];
  62.     FastAppend [] rest -> rest;
  63.     FastAppend [f|r] rest ->[f | !FastAppend r rest];
  64.  
  65. <<
  66. The parallel quicksort algorithm.
  67.  
  68. Sorter sorts a list of integers and returns a tree containing the
  69. sorted result. If the incoming list is smaller than Threshold the
  70. list will be sorted sequentially by SeqSorter whose result will
  71. be stored in a leaf of the tree. Otherwise the parallel algorithm
  72. (ParSorter) will be called, which will result in a binary tree of
  73. processes of which the rootnodes represent a value, the left branch
  74. is a process sorting the values smaller than the rootvalue and the
  75. right branch is a process sorting the values greater than the rootvalue.
  76. >>
  77.  
  78. ::  Sorter [INT] -> SortResult INT;
  79.     Sorter list -> Leaf (SeqSorter list) , IF Smaller list Threshold
  80.                 -> ParSorter list;
  81.  
  82. ::  ParSorter [INT] -> SortResult INT;
  83.     ParSorter [f|r] -> Tree f left right,
  84.                        left:  {P} Sorter small,
  85.                        right: {P} Sorter large,
  86.                        small: {I} Filter r (>= f),
  87.                        large: {I} Filter r (< f);
  88.  
  89. ::  Filter [x] (=> x BOOL) -> [x];
  90.     Filter []    op -> [];
  91.     Filter [f|r] op -> [f | {I} Filter r op] , IF op f
  92.                     -> Filter r op;
  93.  
  94. ::  SeqSorter [INT] -> [INT];
  95.     SeqSorter []    -> [];
  96.     SeqSorter [f|r] -> FastAppend (SeqSorter small) [f|SeqSorter large],
  97.                        (small,large): Split f r [] [];
  98.                               
  99. ::  Split INT [INT] [INT] [INT] -> ([INT],[INT]);
  100.     Split el [] left right      -> (left,right);
  101.     Split el [f|r] left right   -> Split el r [f|left] right , IF < f el
  102.                                 -> Split el r left [f|right];
  103.     
  104. ==  WalkTree transforms the tree that is the result of the sorting process
  105. ==  into a sorted list of integers.
  106.  
  107. ::  WalkTree (SortResult x) -> [x];
  108.     WalkTree (Leaf list)    -> list;
  109.     WalkTree (Tree f l r)   -> FastAppend (WalkTree l) [f|WalkTree r];      
  110.  
  111. ==  The Start rule: Sort the unsorted list and transform the result into a list.
  112.  
  113. ::  Start -> [INT];
  114.     Start -> WalkTree sortresult,
  115.              sortresult: Sorter list,
  116.              list:       UnsortedList;
  117.